# include <stdio.h>
# include <stdlib.h>

typedef struct FileDescriptor {
	char fileName[50];
	char filePath[100];
	char fileType[5];
	int size;
	//Location Block Number
}fd;

typedef struct BST_node{
	char fileName[50];
	struct BST_node * leftChild;
	struct BST_node * rightSibling;
} node;

void copyString (char *str1, char *str2) {
	int i = 0;
	//str1 = (char *) malloc (50 * sizeof(char));
	while (*(str2 + i)){
		*(str1 + i) = *(str2 + i);
		i++;
	}
	*(str1 + i) = '\0';
}

char *split(char *fname) {
	char str[50], *str1;
	str1 = (char *) malloc (50 * sizeof(char));
	int i = 0, j = 0;	
	if(fname[i] == '/')
		i = 1;
	while (*(fname + i) != '/') {
		*(str + j) = *(fname + i);
		i++;
		j++;
	}
	*(str + j) = '\0';
	copyString(str1, str);
	return str1;
}

char *truncateLeft(char *fn, int length) {
	fn = fn + length + 1;
	return fn;
}

int stringLength (char *str) {
	int i = 0;
	while(*(str + i))
		i++;
	return i;
}

char *strconcat (char *str1, char *str2) {
	char *str3 = (char *)malloc(sizeof(stringLength(str2)));
	int i = 0;
	int j = 0;
	copyString (str3, str2);
	while (*(str1 + j)) {
		*(str2 + i) = *(str1 + j);
		i++;
		j++;
	}
	j = 0;
	while (*(str3 + j)) {
		*(str2 + i) = *(str3 + j);
		i++;
		j++;
	}
	*(str2 + i) = '\0';
	return str2;
}

char *checkRoot (char *fname) {

      
	char *str, str1[] = "/root", *str2;
	str = (char *) malloc (50 * sizeof(char));
	str2 = (char *) malloc (50 * sizeof(char));
	str = split (fname);
	//copyString(str2, fname);
	if (strcmp(str, "root"))
		str2 = strconcat(str1, fname);
printf("%s",str2);
	//copyString(str2, fname);
	return str2; 
      
}

node *insertNode (node *root,char *fname) {
	char *fn, *fileName, *fname1;
	node *temp = root;
	node *newNode, *temp1, *parent;
	fileName = fname;
	printf("%s\t", fname);
	//fname = (char *) malloc (50 * sizeof(char));
	fname = checkRoot (fname);
	printf("%s\n", fname);
	newNode = (node *) malloc (sizeof(struct BST_node));
	//newNode -> fileName = '\0';
	newNode -> leftChild = NULL;
	newNode -> rightSibling = NULL;
	if (temp == NULL){
		root = newNode;
		fn = split(fname);
		copyString(root -> fileName, fn);
		root = insertNode (root, fileName);
	}
	else {
		fn = split(fname);
		parent = temp;
		while (temp){
			temp1 = temp;
			if ( !strcmp(temp -> fileName, fn)) {
				parent = temp;
				if (temp -> leftChild) {
					temp = temp -> leftChild;
					fname = truncateLeft (fname, stringLength(fn));
					fn = split (fname);
				}
				else {
					fname = truncateLeft (fname, stringLength(fn));
					fn = split (fname);
					if(*fn){
						parent -> leftChild = newNode;
						copyString(newNode -> fileName, fn);
						root = insertNode (root, fileName);
					}
				}
			}
			else {
				/*if (temp == root && temp -> rightSibling == NULL){
					temp1 -> rightSibling = newNode;
					copyString(newNode -> fileName, fn);
					root = insertNode (root, fileName);
				}*/
				temp = temp -> rightSibling;
			}
		}
		if(temp1 != parent) {
			temp1 -> rightSibling = newNode;
			copyString(newNode -> fileName, fn);
			root = insertNode (root, fileName);
		}
	}
	return root;
}
/*
node *nextPredecessor (node *current) {
	node *temp = current, *preNode;
	if (temp -> leftChild) {
		preNode = temp;
		temp = temp -> leftChild;
		while (temp -> rightSibling) {
			preNode = temp;
			temp = temp -> rightSibling;
		}
		if (preNode -> fileName != current -> fileName)
			preNode -> rightSibling = temp -> leftChild;
		else
			preNode -> leftChild = temp -> leftChild;
		return temp;
	}
	else
		return NULL;
}

node *nextSuccessor (node *current) {
	node *temp = current, *preNode;
	if (temp -> rightSibling) {
		preNode = temp;
		temp = temp -> rightSibling;
		while (temp -> leftChild) {
			preNode = temp;
			temp = temp -> leftChild;
		}
		if (preNode -> fileName != current -> fileName)
			preNode -> leftChild = temp -> rightSibling;
		else
			preNode -> rightSibling = temp -> rightSibling;
		return temp;
	}
	else
		return nextPredecessor(current);
}

node *deleteNode (node *root, int x) {
	node *temp = root;
	node *nextSucc, *preNode, *temp1;
	
	while (temp){
		temp1 = temp;
		if (x < temp -> fileName)
			temp = temp -> leftChild;
		else if ( x > temp -> fileName)
			temp = temp -> rightSibling;
		else {
			nextSucc = nextSuccessor(temp);
			if (preNode -> fileName < temp -> fileName)
				preNode -> rightSibling = nextSucc;
			else
				preNode -> leftChild = nextSucc;
			if (nextSucc) {
				nextSucc -> leftChild = temp -> leftChild;
				nextSucc -> rightSibling = temp -> rightSibling;
			}
			free (temp);
			break;
		}
		preNode = temp1;
	}
	return root;
}

void searchNode (node *root, int x) {
	node *temp = root;
	
	while (temp){
		if (temp -> fileName > x)
			temp = temp -> leftChild;
		else if (temp -> fileName < x)
			temp = temp -> rightSibling;
		else if (temp -> fileName == x) {
			printf ("\nItem %d found\n", x);
			return;
		}
	}
	printf ("\nItem %d not found\n", x);
}
*/
void inOrder (node *root) {
	if (root == NULL)
		return;
	inOrder (root -> leftChild);
	printf("%s\n", root -> fileName );
	inOrder (root -> rightSibling);
}

void preOrder (node *root) {
	if (root == NULL)
		return;
	printf("%s\n", root -> fileName );
	preOrder (root -> leftChild);
	preOrder (root -> rightSibling);
}

void postOrder (node *root) {
	if (root == NULL)
		return;
	postOrder (root -> leftChild);
	postOrder (root -> rightSibling);
	printf("%s\n", root -> fileName );
}
/*
int main() {
	node *root = NULL;
	root = insertNode (root, "/home/abc1/a.txt");
	root = insertNode (root, "/home/abc1/b.txt");
	root = insertNode (root,  "/home/abc1/d.txt");
	root = insertNode (root,  "/home/abc1/e.txt");
	root = insertNode (root,  "/home/abc3/a1.txt");
	root = insertNode (root,  "/home/abc3/a2.txt");
	root = insertNode (root,  "/home/abc3/a3.txt");
	root = insertNode (root,  "/user/abc1/abb.txt");
	root = insertNode (root,  "/user/abc1/a.txt");
	printf("\nPre Order \n");
	preOrder (root);
	printf("\nIn Order \n");
	inOrder (root);
	printf("\nPost Order \n");
	postOrder (root);
	//deleteNode (root, 4);
	/*printf("\nPre Order \n");
	preOrder (root);
	printf("\nIn Order \n");
	inOrder (root);
	printf("\nPost Order \n");
	postOrder (root);*/
	//searchNode (root, 7);
	//searchNode (root, 9);
/*	return 0;
}*/
